package src.question86;

/**
 86. 分隔链表
 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，
 使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
 你应当 保留 两个分区中每个节点的初始相对位置。
 示例 1：
 输入：head = [1,4,3,2,5,2], x = 3
 输出：[1,2,2,4,3,5]
 示例 2：
 输入：head = [2,1], x = 2
 输出：[1,2]
 提示：
 链表中节点的数目在范围 [0, 200] 内
 -100 <= Node.val <= 100
 -200 <= x <= 200
 */
public class LeetCode86 {
    public static void main(String[] args) {
        Solution solution = new Solution();

        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(4);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(2);
        ListNode partition = solution.partition(head, 3);
        while (partition !=null) {
            System.out.print(partition.val + " ");
            partition = partition.next;
        }


    }
}

class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode leftNode = new ListNode(0);
        ListNode leftNodeHead = leftNode;
        ListNode rightNode = new ListNode(0);
        ListNode rightNodeHead = rightNode;
        while (head != null) {
            if (head.val < x) {
                leftNode.next = head;
                leftNode = leftNode.next;
            } else {
                rightNode.next = head;
                rightNode = rightNode.next;
            }
            head = head.next;
        }
        rightNode.next = null;
        leftNode.next = rightNodeHead.next;
        return leftNodeHead.next;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
